Người Pháp mộ lính người Việt để đánh triều đình Huế từ năm 1860 khi họ chiếm được Đà Nẵng. Nhóm lính này không được tín nhiệm vì tỷ lệ đào ngũ khá cao. Mãi đến năm 1879 sau khi người Pháp đánh chiếm được toàn đất Nam Kỳ thì mới thành lập đội ngũ lính bản xứ hẳn hoi, tổng cộng là 1.700 người. Nhiệm vụ chính là phòng giữ và canh gác.

Năm 1882 khi vụ Henri Rivière đem quân ra đánh phá Bắc Kỳ rồi bị mai phục chết ở Cầu Giấy vào Tháng Năm năm 1883 thì thống soái Nam Kỳ mới có lệnh chuyển lính khố đỏ Nam Kỳ ra Bắc để giúp quân đội Pháp. Trận đánh thành Sơn Tây được xem là trận giao chiến đầu tiên của lính khố đỏ. Sang năm 1884 với sắc lệnh ngày 13 Tháng Năm thì mới lập thêm đội lính khố đỏ Bắc Kỳ, chủ yếu mộ lính từ cộng đồng giáo dân theo đạo Thiên Chúa; ít lâu sau thì người Pháp mở rộng việc thu nạp, không phân biệt lương dân hay giáo dân.

Đội lính khố đỏ Bắc Kỳ đông hơn, tổ chức thành bốn trung đoàn (regiment) với tổng số 14.000 lính[1] trong khi lính Nam Kỳ chỉ có một trung đoàn. Mỗi trung đoàn có bốn tiểu đoàn (bataillon) 1.000 người. Năm 1895 thì tăng lên thành năm trung đoàn lính khố đỏ Bắc Kỳ. Trung đoàn thứ năm có một số lớn dân thiểu số gốc Thổ và Mường. Như vậy tới năm 1886, lực lượng lính tập bản xứ chiếm tới một nửa trong số khoảng 30 ngàn quân Pháp có mặt tại Bắc Kỳ, tạo điều kiện cho Khâm sứ Pháp Paul Bert có thể rút dần một số đơn vị lính Âu về nước[2].Lính khố đỏ Nam kỳ tới năm 1905 cũng có ít nhất 4 trung đoàn.

Trong số các trung đoàn bộ binh Bắc kỳ, ba trung đoàn đầu tiên thuộc biên chế do Hải quân Pháp trả lương; trung đoàn thứ tư thuộc Bộ Binh. Ngoài tra, tồn tại trong một thời gian ngắn trước khi bị giải tán, còn có một lực lượng lính Truy kích An Nam (Chasseurs annamites), lương trích từ ngân khố của triều đình Huế.

Cấp chỉ huy lính khố đỏ tất cả đều là người Pháp. Mỗi trung đoàn có một viên đại tá (colonel) cầm lệnh. Mỗi tiểu đoàn (bataillon) có một thiếu tá (major) và liên đoàn (compagnie) thì có đại úy (capitaine, tiếng Việt thời đó còn gọi là "quan ba") chỉ huy.

Lính bản xứ chỉ được thăng cao nhất là làm phó quản (adjudant). Kém hơn là đội (sergent nay tương đương với trung sĩ) hoặc cai (caporal) mà thôi.[3]

Thời Đệ nhất Thế chiến có khoảng 43.000 lính tập cùng với 49.000 lính thợ được chuyển sang Pháp một số bỏ mình ở Pháp, nay còn đải tưởng niệm ở nghĩa trang Saint-Pierre ở Aix-en-Provence.[4]